This invention relates to a method and scheme for congestion management in two-way data satellite communications with residential and business terminalsxe2x80x94hereinafter referred to as Broadcast Rate Control Allocation (BRCA). More particularly, the invention is directed to a method for supporting efficient transport for Available Bit Rate (ABR) services over a satellite, wherein the satellite switch provides feedback (which is broadcast to all terminals), in order to control the rate at which terminals can send their data to satellite.
While the particular embodiment in this invention is directed to Geostationary Earth Orbit (GEO) satellites supporting Asynchronous Transport Mode (ATM) services, it should be appreciated that the invention is applicable to the transport of data in other (than ATM) packet formats over satellites in other (than GEO) orbits, provided that a grade of service for data is specified, similar to that specified for ABR services.
Broadband satellite networks are becoming an important segment of the global communication infrastructure. They are required to provide seamless integration of applications and services that have traditionally been available via terrestrial networks. In order to ensure inter-operability between terrestrial and satellite networks, efforts have been made to expand/adapt the existing protocols for terrestrial networks to satellite environment. These efforts have not always led to full utilization of satellite resources, as these protocols have been optimized for terrestrial applications. New protocols, specifically tailored to satellite environment are therefore required.
In a typical satellite network the satellite bandwidth, buffer and computational resources are shared by a relatively large population of terminals, connected to end-users and sending traffic corresponding to various applications (voice, video, data). The traffic associated with data applications exhibits high variability and unpredictability. Each connection requires certain satellite bandwidth, in order to guarantee the Quality of Service (QoS) expected by the end user. Given the diversity of traffic characteristics and of bandwidth and QoS requirements associated with different applications, future satellite networks will use on- board fast packet switching, in order to ensure efficient use of satellite resources while guaranteeing QoS for all connections. ATM establishes itself as the preferred transport mode in today""s Broadband Integrated Services Digital Networks (B-ISDN), including the satellite networks. It is therefore considered in this invention that the traffic will be transported over the satellite in ATM-like packets, i.e. packets which preserve the structure of standard ATM cells, while adding a satellite-specific header to support satellite-specific functions, such as uplink scheduling and on-board routing. A standard ATM cell is fifty three-byte long, consisting of a five-byte header and a forty eight-byte information field, also referred to as payload. Depending on the particular implementation, the On-Bard Processor (OBP) may use some information from the ATM header, in addition to the information contained in the satellite-specific header. After being processed, the ATM packets are stripped of the satellite- specific header before being sent to their downlink destinations. The information in the ATM header may be preserved in order to allow for easy integration of the satellite into a broader ATM network.
The use of on-board switching (of ATM-like packets) allows for statisical multiplexing of the traffic corresponding to various connections, thus improving satellite resources utilization. The most valuable resource is the bandwidth (capacity) of the air interface between terminals and satellite, on both uplink (UL) and downlink (DL). In contrast to the wired networks, in a satellite network the physical medium (link) is shared by all active terminals logged onto the system. Advanced multiple access or Medium Access Control (MAC) protocols are therefore required to provide efficient, dynamic and fair sharing of satellite bandwidth among these terminals, while supporting various levels of QoS guarantees (depending on application), given to sources as part of the traffic contract. A system for efficient transport of multimedia traffic over a satellite network is described in U.S. patent application Ser. No. 08/669,609, submitted by EMS Aerospace Limited (C. Black et al.) on Jun. 24 1998 and entitled xe2x80x9cData Communication Satellite System and Method of Carrying Multi-Media Trafficxe2x80x9d. In this system a key element in achieving efficient resource utilization is a novel Dynamic Uplink Access Protocol (DUAP).
The DUAP proposed by EMS is from the Combined Free and Demand Assignment Multiple Access (CFDAMA) family of protocols, which are based on Multiple Frequency-Time Division Multiple Access (MF-TDMA) transmission frame, capable of providing efficient and flexible bandwidth utilization. Protocols from this family distribute transmission bandwidth (capacity) based mainly on demands (or requests) from terminals, following a fairness algorithm. The bandwidth left after all requests have been satisfied is distributed a freely across terminal population.
EMS""s implementation of CF-DAMA protocol is based on four capacity request/assignment mechanisms (or strategies), each receiving a different priority from the UL scheduler, an entity responsible for capacity allocation to terminals which can be located on board the satellite or on ground. The request strategies lead to four types of capacity (or channels), tailored to match the needs and priorities of various ATM service classes: Reserved Capacity (RC), Rate-Based Dynamic Capacity (RBDC), Volume-Based Dynamic Capacity (VBDC) and Free Capacity (FC). The capacity types are essential for the invention described in the application, therefore they are briefly reviewed in the following paragraphs.
In the RC assignment strategy a terminal states its need for UL and DL capacity at connection set-up time, in terms of a fixed number of payload slots per frame. If the connection is admitted by the network controller, the terminal will have the requested number of time slots assigned to it every frame (reserved) for the duration of the connection, so that the traffic is not subjected to any delay except for the propagation delay (no scheduling and queuing involved). The network controller must ensure (at connection set-up time) that the total RC for all connections does not exceed the total system capacity. This strategy is aimed toward real-time (RT) connections, such as Constant Bit Rate (CBR) and real time-Variable Bit Rate (rt-VBR), which cannot tolerate or have strict constraints on delay and delay variation (e.g. voice connections), and is especially suitable for applications with smooth traffic characteristics.
In the RBDC assignment strategy, a terminal explicitly requests a number of UL payload slots in each frame. A request remains effective for a number of frames (until it is updated by the terminal or as long as it has not timed out), so that the request is also implicit. In one implementation option of the RBDC strategy, the UL capacity is guaranteed by the scheduler up to the maxRBDC value negotiated at connection set-up time. In contrast to the RC strategy, the RBDC strategy allows for statistical multiplexing among terminals, thus resulting in a more efficient use of satellite bandwidth. Nevertheless, the network controller must also ensure that total RC and maxRBDC of all terminals do not exceed the total available UL and DL capacity. The RBDC strategy can be used for non-real-time connections, such as non real time Variable Bit Rate (nrt-VBR) connections, if scheduling delay is tolerated, and ABR connections.
In the VBDC assignment strategy, a terminal signals its request in terms of total number of UL payload slots required to empty its queue. The network, however, does not provide any guarantee on capacity availability. The UL scheduler will do its best to satisfy a request of this type. The request remains effective as long as not all requested time slots have been granted. This strategy is directed toward Jitter Tolerant (JT) connections and is especially suited for bursty traffic. It allows for a great deal of statistical multiplexing and thus may contribute to a very efficient use of network resources. VBDC strategy may be implemented with two priorities: the high priority strategy (HP-VBDC) and the low priority strategy (LP-VBDC). LP-VBDC is used for UBR services, while HP-VBDC can be used for ABR services, perhaps in combination with one of the first two request strategies (i.e. RC or RBDC).
Finally, in the Free Capacity Allocation (FCA) strategy the uplink scheduler attempts to maximize UL capacity utilization by distributing the unrequested UL capacity across all terminals. This strategy ranks the lowest among all four, i.e. the scheduler will satisfy all RC, RBDC and VBDC requests before assigning free capacity. Unlike the previous assignment strategies, ground terminals have no control in obtaining free capacity.
The order in which terminals are granted access to VBDC and FCA capacity is carried in a systematic fashion (round robin scheduling), in order to ensure fairness. This is based on a terminal table maintained in the uplink scheduler, which is a database of ground terminals currently registered in the network. The table is arranged in a circular linked-list fashion, and each entry in the table contains information related to a specific ground terminal, such as its configured RC, its maximum and currently requested RBDC and two pointers to terminal""s HP-VBDC and LP-VBDC request queues. The scheduler guarantees capacity assignment for each terminal""s RC and RBDC requests. Hence, access fairness is not relevant for the first two scheduling strategies, but only for VBDC and FCA. The process of distributing uplink capacity to ground terminals, called the assignment process, involves a few passes through the terminal table. In the first pass, the scheduler counts the uplink capacity requested with each of the request strategies (other than FCA). In the second pass, the scheduler inspects each terminal entry in the table starting from the head entry of the linked list. During each inspection, the scheduler will satisfy the entry""s RC and RBDC requests. It also attempts to satisfy each entry""s HP-VBDC and LP-VBDC requests in full, as long as uplink capacity is still available. An entry that is fully serviced it moved to the end of the linked list. During this second pass, the scheduler may place a tag on one entry for each of the non-guaranteed bandwidth request strategies, i.e. the low and high priority VBDC and the FCA strategies. A tagged entry corresponding to one of these request strategies is the last entry receiving capacity assignment through that particular request strategy. Then, at the end of the pass, the next entry after the highest-priority tagged entry will be made the head of the linked list. Hence, the two-pass assignment process ensures that, at the end of the process, the entry with the highest priority ungranted request is made the head of the terminal table linked list, so it will be the first to be inspected in the next assignment process (next frame).
The assignments are signaled to terminals every MF-TDMA frame, by using Burst Time Plans (BTPs). A BTP specifies for each frame the number and position (within frame) of the slots assigned to every terminal, regardless of the type of traffic for which assignments have been made. The UL scheduler keeps in its data base copies of BTPs for the last scheduling delay (one round-trip delay if the UL scheduler is located on-board the satellite).
During its lifetime, a connect may utilize more than one request strategy. Since each request strategy is aimed to providing a different level of QoS guarantee, the UL access protocol has the capability to support flexible QoS, matched to user""s needs. As the request strategies are quite different from each other, they can provide, as a whole, integrated support for both circuit-switched and packet-switched services (both connection-oriented and connectionless) and for a variety of multimedia applications.
Due to the statistical multiplexing of data traffic, congestion can occur on-board the satellite, leading to performance degradation (cell loss or excessive delay). Congestion is a dynamic problem arising from changing network loading conditions. It is defined as the state in which the network is not able to meet the required QoS for already admitted connections. The congestion-related effects are aggravated by the large bandwidth-delay product specific to GEO satellites. Effective congestion avoidance/control schemes are needed to ensure stable operation of the satellite network, fairness and efficiency in the utilization of satellite bandwidth.
The effectiveness of congestion control/avoidance schemes is measured by their ability to achieve a number of objectives, as discussed below.
Efficiency/Delay
Efficiency is measured by the ability of a scheme to ensure high utilization of link capacity, while providing the level of QoS guarantee negotiated for the connection. QoS is specified in terms of performance metrics such as Cell Loss Ratio (CLR) and traffic delay induced by the scheme. The CLR is determined by the queuing performance of the servers at the multiplexing points (e.g. in the switch on-board the satellite) under the loading condition with given data traffic. The traffic associated with today""s data applications is characterized by high variability and unpredictability. The ratio between peak and average cell rate can be very large, and periods of high intensity can randomly alternate with periods of inactivity or low activity. During high intensity periods the traffic will be queued in the switch buffers. It is the instantaneous size of the queue relative to the size of the buffer which will ultimately determine the CLR. The queue size will also determine the amount of delay induced by the scheme. The queue size depends on system loading and traffic statistical properties. Loading on both uplink and downlink channels should be taken into consideration. An efficient scheme should ensure high utilization of both uplink and downlink capacity, while not exceeding the specified CLR and/or queuing delay. The efficiency and CLR/delay requirements are contradictory, therefore a trade-off is normally made. The delay increases almost linearly with the load, until the maximum downlink capacity is reached. Any further increase in load would result in packet loss or excessive delay, as a result of queue build-up in the switch. In a GEO satellite environment the end-to-end delay is dominated by the propagation delay and uplink scheduling delay, so that the queuing delay might be less relevant if properly controlled. Both CLR and queuing delay are associated with the queue management function aimed at achieving stable queues, as discussed below.
Fairness
In general fairness is understood as giving the same chances to all contending sources in the use of common resources, such as bandwidth. In a satellite system it is desirable to reinforce fairness in both uplink and downlink channels (understood in this context as RF channels characterized by well defined bandwidth or capacity), so fair rates are separately calculated for each uplink channel and each downlink channel. For a given connection the fair rate will be taken as the minimum between the uplink and downlink fair rates. Each terminal should be allowed to adjust its rate (increase or decrease) function of the network loading conditions.
Stable Queue Size
Stable queue size is maintained by queue size management, in order to avoid that the instantaneous queue size exceeds the switch buffer size (which is key to meeting the CLR requirements). Due to physical and cost limitations associated with the on-board hardware, the size of the switch buffers should be maintained at a minimum. The minimum buffer size depends on traffic characteristics (variability) at buffer""s input and on the desired responsiveness of the congestion control scheme. It is upper-bounded by the need to store data corresponding to one round trip delay, which is the minimum response time in a feedback scheme. As for a GEO satellite this upper bound can be quite high, well designed rules should govern the behavior of various network elements (e.g. rate increases/decreases in terminals).
Good Steady State and Transient Behavior
Steady state is encountered when ground terminals have always traffic to send (i.e. their buffers are never empty). As a result the system is consistently overloaded or underloaded, and little oscillation is expected in scheme""s behavior (e.g. rate, queue size). This is a rare situation, as the traffic normally exhibits high variability. The congestion control scheme cannot and is not required to respond to these very rapid instantaneous variations (happening over time scales well below the control loop response time). Some of these variations are xe2x80x9csmoothed-outxe2x80x9d in the process of uplink scheduling (especially at high loads). Additional smoothing is intentionally introduced by the rules defined for rate increase/decrease in terminals, consistent with the queue management strategy. By contrast, at low loading condition the entire variability of the offered traffic can be seen at the input of the switch buffers. The congestion control scheme should therefore respond differently in different loading conditions, but always trying to maintain stable queue size and to ensure optimum use of satellite resources. The transient behavior can be tested with ON/OFF sources or with sources which are activated at predefined times.
Robustness
A congestion control scheme is required to remain effective when the ABR traffic is mixed with other traffic classes, such as rt-VBR and UBR (case in which the capacity available for ABR services is no longer fixed), or when high variability in network loading is encountered. The scheme should also be insensitive to slight miss-tuning of parameters (due to errors in measurements and/or calculations) and should remain stable in the case of loss of control messages.
Minimal On-board Complexity
Due to physical and cost limitations of on-board hardware/software, the on-board monitoring and computing functions of a congested control scheme should be reduced to a minimum, by proper selection of the number of parameters to be monitored and of the calculations to be performed on-board. Any effort should be made to transfer to ground terminals some of the calculation tasks. The computing functions should not be sensitive to network loading condition (such as the number of ABR sources).
From all ATM service classes, the ABR class is designed to efficiently support data traffic. The ABR class is characterized by specified Peak Cell Rate (PCR) and Minimum Cell Rate (MCR) as traffic descriptors. The peak-to-peak Cell Delay Variation (CDV) and max Cell Transfer Delay (CTD) are not specified as QoS measures. The Cell Loss Ratio (CLR) can be specified at system level (it is system-specific). The efficiency of a congestion control scheme will be judged by its ability to support ABR services with given CLR tolerance. CLR dependence on buffer size is the main tool used in the dimensioning of the on-board buffers.
Efficiency in supporting d traffic is ensured by subjecting the ABR traffic to congestion/flow control. ATM Forum has adopted rate-based schemes as standard for congestion control for ABR services. In a rate-based scheme the sources are provided with feedback information from the switches (reflecting their loading conditions), specifying the rates at which they can send their traffic. The ATM Traffic Management Specification V4.0 (TM4.0) defines strict rules concerning source and destination behavior, while for the switch behavior a few options are recommended and only coarsely specified. One of these options, namely the Explicit Rate Indication for Congestion Avoidance (ERICA) algorithm, has gained popularity in the past years, especially for terrestrial networks [see U.S. Pat. No. 5,805,577 entitled xe2x80x9cERICA: Explicit Rate Indication for Congestion Avoidance in ATM Networksxe2x80x9d, by Jain et al.].
ERICA algorithm is concerned with fair and efficient allocation of network resources to all contending sources, while preventing buffer overflow and excessive loss (or delay) of packets. This is basically achieved by controlling the transmission rates in order to reduce the flow of traffic entering the network. ERICA relies on monitoring of the cell arrival rates (as a primary metric) for ABR and higher priority traffic and of the available capacity for ABR traffic, which are then used to periodically calculate (every averaging interval) the fair share and the Explicit Rate (ER) at which each terminal is allowed to send its traffic. The ERs (one for each ABR virtual connection) are signaled to the sources by using Resource Management (RM) cells. An improved version of ERICA, called ERICA+, also monitors the queue length as a secondary metric, to detect congestion situations and control the queue size. The use of queue size, in conjunction with some threshold value, allows for more efficient capacity utilization (by dynamically modifying the link target rate), while attempting to maintain stable queue size.
The ERICA algorithm is an end-to-end (source-destination) congestion control scheme. Each source generates an RM cell after a given number of traffic cells or after a pre-set time interval has expired. The RM cells carry congestion/flow control information, the key parameters being the Current Cell Rate (CCR) and the ER. Other parameters include RM cell direction (DIR), backward notification (BN), congestion indication (CI) and no increase (NI), which are set or used by various components of the virtual connection (source, switches, destination), in agreement with the behavioral conformity rules defined in TM4.0. The RM cells travel along the network and the destination returns them to the source. Each switch sets the ER to the maximum value it can support, if this is smaller than the current rate (set by other switches). In the scheme called Virtual Source Virtual Destination (VSVD), derived from ERICA, the end-to-end link is split in segments and the flow of traffic is controlled independently within each segment. Consequently the elements of the network (particularly the buffers) will be dimensioned based on the delay-bandwidth product for the segment which contains the network element under consideration and not by the delay-bandwidth product of the whole network. At the splitting points the network will have to behave as virtual source and virtual destination.
ERICA/ERICA+ algorithms have also been adapted to satellite environment and its performance evaluated based on simulation models [see A. Iuoras et al., xe2x80x9cQuality of Service-Oriented Protocols for Resource Management in Packet-Switched Satellitesxe2x80x9d, Fourth KaBand Utilization Conference, Venice, Nov. 2-4, 1998]. ERICA algorithm was implemented in all uplinks (in order to ensure fairness), while ERICA+ was implemented in all downlinks (in order to ensure fairness and stable downlink queues). For both uplinks and downlinks the queuing was performed per downlink destination, while the calculations were performed for each virtual connection (per-VC accounting). The terminal processing required by the algorithm was integrated with the request mechanisms of the UL scheduler. The simulations have shown that ERICA/ERICA+ algorithms can ensure stable network operation, while offering high bandwidth utilization. The required on-board buffer size, however, can be rather large, and the overall throughput can suffer (at high network loads) due to the high overhead introduced by the RM cells.
Consequently, there is a need to provide a more efficient method for ABR traffic management in satellite networks. This method should take advantage of the broadcast nature of the satellite and should take into account the access schemes and switching techniques specific to satellite networks, in order to optimize the utilization of satellite resources while guaranteeing QoS for ABR services.
It is therefore an object of the present invention to provide an efficient method for congestion avoidance on-board the satellite in order to support ABR services with given cell loss tolerance.
It is a further object of the present invention is to exploit the broadcast nature of the satellites in order to provide ground terminals with feedback information required to control their transmission rates.
It is still a further object of the present invention to ensure fair and efficient allocation of satellite resources to all contending sources.
Another object of the present invention is to integrate the congestion avoidance scheme with the multiple access scheme and switching techniques specific to satellite networks, in order to achieve efficiency in satellite resource utilization.
Yet another object of the present invention is to reduce the on-board computational requirements of the congestion avoidance scheme, by transferring some of the calculations to the ground terminals.
A final object of the present invention is to define the rules for terminal behavior in agreement with the switch algorithm. According to these rules the control should be exercised on the requests (of rates at which terminals are allowed to send their traffic) and not on the transmission rates, in order to avoid any waste of capacity.
According to one aspect of the present invention, a method is proposed to efficiently support ABR services over packet-switched satellite networks. Supporting ABR services means providing minimum capacity guarantee and flow control for ABR sources, in order to prevent excessive cell loss or delay for ABR traffic, resulting from congestion of on-board satellite resources. The proposed method for congestion avoidance relies on dynamic close-loop reactive flow control to respond to changes in network loading conditions. It requires continuous monitoring of cell arrival rates (for ABR and higher priority traffic), ABR capacity requests, downlink buffer occupancy and number of ABR sources, in order to calculate the fair rate and the amount of rate adaptation in each uplink channel and each downlink channel. It then determines the final fair rate and rate adaptation (increase, decrease or no change) for each UL-DL combination.
The proposed switch algorithm, which is responsible for the calculation of fair rate and rate adaptation, is a rate-based flow control algorithm like the ERICA/ERICA+ algorithm developed for ATM networks, but unlike ERICA/ERICA+ it does not rely on the flow controlxe2x80x94related functionality of an ATM switch and does not use RM cells to carry congestion-related information to terminals. It uses instead regular data cells to broadcast to all terminals, as per another object of this invention, the information that controls the allocation of transmission rates of ABR terminals. The new method and algorithm are therefore called Broadcast Rate Control Allocation (BRCA). The terminals use the appropriate information from the control messages (which are periodically updated, every averaging interval) to determine the amount of uplink capacity they are allowed to request in each frame. The requests for capacity are handled by the uplink scheduler, which implements the functionality of the uplink access protocol. The rate-based flow control in terminals is thus fully integrated with the request mechanisms of the uplink access protocol, according to another object of the present invention. By exercising the rate control on the request rates (and not on the transmission rates), the waste of uplink capacity is minimized. Once the requests are granted (by the UL scheduler), the terminals are responsible for distributing the assigned capacity to various traffic classes and for transmitting the traffic packets.
The UL access protocol considered in the preferred embodiment of the present invention, referred to as DUAP, is EMS""s version of CFDAMA protocol, which was briefly introduced in the background section. Due to its request/assignment mechanisms DUAP is capable of providing flexible and efficient utilization of uplink capacity while supporting a diversity of services, including ABR services. The present invention can be used with any other uplink access protocol capable of supporting ABR services, which means providing capacity guarantee up to MCR and capacity on demand subjected to flow control for rates in excess of MCR.
BRCA scheme is based on the view of the satellite system as a tandem of two-server queuing system. The first server is the uplink scheduler, with queuing performed in ground terminals, while the second server is the downlink scheduler, with queuing performed on-board the satellite. BRCA algorithm is implemented in each uplink channel and each downlink channel. In the uplink channels it is concerned with reaching fairness among all contending sources, while in the downlink channels it is concerned with reaching fairness and optimum loading conditions. In order to reach fairness the algorithm calculates the fair rate and the required amount of rate adaptation for each uplink channel and each downlink channel, based on measurement results from previous averaging interval. In order to achieve optimum loading in the downlink channels the algorithm attempts to keep the load close to a target value and the queue size below a threshold value.
In BRCA algorithm the final rate and the amount of rate adaptation are determined for each uplink-downlink combination and not for each virtual connection (VC), as in the case of ATM-compatible schemes, which results in reduced on-board computational requirements, as per another object of this invention. The signaling needs will be significantly reduced as well, with positive impact on algorithm""s overall bandwidth efficiency. By contrast, the terminals are required to calculate for themselves, from the set of control messages, the Allowed Cell Rates (ACR) at which the requests for ABR capacity can be made.
The full scope of applicability of the present invention will become more apparent from the detailed description and the examples provided below. It should be understood that the detailed description and the specific examples, while indicating preferred embodiments of the invention, are given for illustration only, since various changes and modifications within the spirit of the invention can be imagined.